1. Field of the Invention
The present invention relates to persistent object systems, and in particular to sizing an object cache using feedback from the execution of a persistent object system.
Sun, Sun Microsystems, the Sun logo, Solaris, Java and all Java-based trademarks and logos are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. All SPARC trademarks are used under license and are trademarks of SPARC International, Inc. in the United States and other countries. Products bearing SPARC trademarks are based upon an architecture developed by Sun Microsystems, Inc. Gemstone/J is a trademark or registered trademark of GemStone Systems Inc. in the United States and other countries. Motorola and 680X0 are trademarks or registered trademarks of Motorola Inc in the United States and other countries. Intel, 80X86, and Pentium are trademarks or registered trademarks of Intel Corporation in the United States and other countries.
2. Background Art
Persistent object systems are designed to handle data that continues to exist, even after the process that created it has stopped executing. In contrast, transient object systems are designed to handle data only during the execution of the process that created the object. A heap is an area of memory reserved for objects that are created at runtimexe2x80x94that is, when the program actually executes. The persistent object system provides the illusion of a very large object heap because it is not limited only to objects that are created at runtime. Instead, a persistent object system may operate on both transient objects and persistent objects which are automatically backed up by secondary storage. The persistent objects may be stored in memory separately from transient objects or may be stored together in the heap.
Persistent objects are automatically saved to secondary storage, typically a stable storage medium such as a disk drive, and fetched from secondary storage into virtual memory on demand. The persistent object system implements automatic secondary storage management. Objects are accessed uniformly in virtual memory, regardless of whether they are transient or persistent. Persistent objects are written to storage when the program performs a xe2x80x9ccheckpoint. xe2x80x9d A checkpoint is a snapshot of the state of the object at that moment in time. A complete description of one embodiment of a checkpointing scheme is described in co-pending U.S. patent application entitled xe2x80x9cMethod and Apparatus for Hybrid Checkpointingxe2x80x9d Ser. No. 09/652,217 filed on Aug. 31, 2000, now U.S. Pat. No. 6,275,443, issued Aug. 14, 2001, assigned to the assignee of the present application, and hereby fully incorporated into the present application by reference. Objects are automatically read (faulted in) from the store when the program refers to them. This allows a long lived program""s computation to survive in stable storage, across multiple executions, and despite system failures. An example of a persistent object platform is described below.
Persistent Object Platform
An example of a persistent object platform is one that implements the Java platform. A program which utilizes Java technology is composed of a number of classes and interfaces. Unlike many programming languages, in which a program is compiled into machine-dependent, executable program code, programs which utilize Java technology are compiled into machine independent bytecode class files. Each class contains code and data in a platform-independent format called the class file format. The computer system acting as the execution vehicle contains a program called a virtual machine, which is responsible for executing the code in classes. The virtual machine provides a level of abstraction between the machine independence of the bytecode classes and the machine-dependent instruction set of the underlying computer hardware. FIG. 1 is a block diagram illustrating a sample network application environment, for instance a Java network application environment, comprising a client platform 102 coupled over a network 101 to a server 100 for the purpose of accessing class files for execution of an application or applet.
Sample Network Application Environment
In FIG. 1, server 100 comprises development environment 104 for use in creating the class files for a given application. The development environment 104 provides a mechanism, such as an editor and an applet viewer, for generating class files and previewing applets. A set of core classes 103 comprise a library of classes that can be referenced by source files containing other classes. From development environment 104, one or more source files 105 are generated. Source files 105 contain the programmer readable class definitions, including data structures, method implementations and references to other classes. Source files 105 are provided to compiler 106, which compiles source files 105 into compiled xe2x80x9c.classxe2x80x9d files 107 that contain bytecodes executable by a virtual machine. Bytecode class files 107 are stored (e.g., in temporary or permanent storage) on server 100, and are available for download over network 101.
Client platform 102 contains a virtual machine (VM) 111 which, through the use of available native operating system (O/S) calls 112, is able to execute bytecode class files and execute native O/S calls when necessary during execution. Class files are often identified in applet tags within an HTML (hypertext markup language) document. A web server application 108 is executed on server 100 to respond to HTTP (hypertext transport protocol) requests containing URLs (universal resource locators) to HTML documents, also referred to as xe2x80x9cweb pages.xe2x80x9d When a browser application executing on client platform 102 requests an HTML document, such as by forwarding URL 109 to web server 108, the browser automatically initiates the download of the class files 107 identified in the applet tag of the HTML document. Class files 107 are typically downloaded from the server and loaded into virtual machine 111 individually as needed.
It is typical for the classes of a program to be loaded as late during the program""s execution as possible; they are loaded on demand from the network (stored on a server), or from a local file system, when first referenced during the program""s execution. The virtual machine locates and loads each class file, parses the class file format, allocates memory for the class""s various components, and links the class with other already loaded classes. This process makes the code in the class readily executable by the virtual machine.
Object Cache Management
Objects read from stable storage into virtual memory (xe2x80x9cpersistent objectsxe2x80x9d) are stored in an xe2x80x9cobject cachexe2x80x9d. In general, caches are implemented under the assumption that it is very likely that some object or piece of data will be repeatedly accessed. Access delays are minimized by keeping popular data close to the entity which needs it. A cache comprises a finite area of a computer""s memory and, as stated above, can be combined to contain both transient and persistent objects. Thus, the total space for all memory-resident persistent objects may exceed some proportion of the total cache size, called a xe2x80x9cbudgetxe2x80x9d. When the persistent objects in the cache exceed the size of the budget they must be removed from the cache. Removing such objects from the cache is termed xe2x80x9cevictionxe2x80x9d. Once an object is evicted, it must be read from the store the next time it is needed. Thus, it is important to try to not evict objects that are likely to be used again in the near future. Current eviction schemes are inadequate at determining whether an object marked for eviction is likely to be used in the near future.
Current Schemes for Managing the Object Cache
Using current schemes, a persistent object system""s object cache is implemented either by using a combined heap (i.e., combining the heap with the object cache) or by using a separate storage area. Using a combined heap and object cache is a simpler implementation because a garbage collector can treat persistent objects like other heap objects. Garbage collection is a part of a language""s runtime system, or an add-on library, perhaps assisted by the compiler, the hardware, the operating system, or any combination of the three. The garbage collector automatically determines what memory a program is no longer using, and recycles it for other use. When an object is evicted, references to that object can be updated using the same mechanisms that the garbage collector uses to update references after a garbage collection. Also, unused space in the object cache can be used in the heap, and vice-versa.
On the other hand, using a separate object cache allows persistent objects to be managed separately from transient objects. It allows eviction to be done independently from garbage collection. However, a separate object cache is a more difficult implementation, since the heap will now contain references to a separate storage area, (the object cache), and the garbage collector must be modified to scan those references correctly. When objects are evicted, references to those objects must be updated, and it may not be possible to reuse garbage collector code to do this. If the garbage collection is not exactxe2x80x94that is, if it does not have exact information about the location of every objectxe2x80x94eviction will be harder to implement since it will not be possible to move some objects.
In the prior art, some work has been done on eviction, and several strategies have been used. These strategies include: total eviction, second chance eviction, random eviction, clock-based eviction, and partition-based eviction. In the total eviction scheme, all persistent objects are evicted. In the second chance eviction scheme, at each garbage collection, objects are marked which are likely to need eviction soon and then given a second chance. If the marked objects are not referenced at the next garbage collection, they are evicted. In the random eviction scheme, some percentage of objects are evicted in a random fashion. In the clock-based eviction scheme, objects kept longest in the cache are evicted first. In the partition-based eviction scheme, the object cache is divided into partitions and when eviction is needed, some objects in a partition are evicted. Objects within a partition maybe selected using a second chance strategy, a clock scheme, or some other strategy.
Each strategy differs in how well it evicts objects not likely to be used again in the near future. For example, since total eviction evicts all persistent objects, it tends to perform poorly because it evicts all objects regardless of whether or not they might be needed later. In a total eviction scheme, the evicted objects often need to be accessed again in the near future. This means the objects must be faulted in again from storage. Faulting the object in causes a penalty associated with input and output operations. Second chance eviction performs better than total eviction because it keeps the most recently used objects in the hope that they will be used again. However, second chance eviction may evict too many objects if, for example, the time period chosen is too short and it evicts objects that the program will soon need again.
Random and clock-based eviction both have the trouble that they often evict objects that will be needed soon. Partition-based eviction tends to perform well because it minimizes the number of objects evicted (since only one partition is considered for eviction), and so it retains more objects including those that might be needed again. Furthermore, the objects in the partition having potentially evicted objects can be selected by second chance (or another scheme) that increases the chances of choosing the correct objects to evict.
The various strategies differ in how difficult they are to implement. Random and total eviction are easy to implement. Second chance eviction is only slightly more difficult to implement than random and total eviction. These schemes can easily be implemented in an object cache that is either combined with or separate from the heap. Partition-based eviction is much more difficult to implement. Current partition-based schemes require a separate object cache, and the difficulties implementing this were described above. Using a separate object cache also has the drawback that unused space in the object cache cannot be used by the heap and vice-versa.
One example of a partition-based scheme is Gemstone/J. Gemstone/J implements persistence in the Java technology platform by using a modified version of the Java Hot-Spot performance engine. The separate object cache is called a persistent object memory (POM) and is divided up into partitions. When the POM fills up, the oldest region is garbage collected and reused. In Gemstone/J the size of the POM is fixed: it cannot be varied during a program""s execution based on the behavior and needs of the program. This is disadvantageous because the behavior and needs of different programs and even the same program at different times vary dramatically.
In summary, different schemes have been used to implement and manage object caches. Object caches have been combined with the heap or have used a separate storage area. A number of eviction strategies have been used that differ in how effective they are in keeping objects in the cache that are likely to be used again in the near future. However, all current object cache implementations are fixed size. They do not increase in size when the system needs to keep more persistent objects in memory, and do not shrink when the system needs memory for more important activities. What is needed is a mechanism that enables object caches to grow or shrink according to the requirements of the rest of the persistent object system.
The present invention uses feedback to determine the size of an object cache. The size of the cache, (i.e., its budget), varies and is determined based on feedback from the persistent object system. Persistent objects are evicted from the cache if the storage for persistent objects exceeds the budget. If the storage is less than the budget then persistent objects in the heap are retained while new persistent objects are added to the cache.
One embodiment increases the budget when the feedback indicates that the rate at which persistent objects are being faulted in is high. Another embodiment decreases the budget when the feedback indicates that the rate at which transient objects are being allocated is high. Another embodiment decreases the budget when the feedback indicates that the rate of garbage collection is high.
Using the budget to partition the object cache between transient and persistent objects, various schemes are applied to reduce the number of persistent objects through eviction until the number of persistent objects equals the budget. One embodiment uses a second chance tagging scheme. Another embodiment uses a random eviction scheme. In this way, the present invention utilizes feedback to approximate a solution to the problems associated with attempting to evict only the most necessary persistent objects from the object cache. In one embodiment, the object cache is combined with the heap. In another embodiment, the heap and object cache remain separated.